package 算法.leetcode.bytedance;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author lchenglong
 * @date 2022/5/12
 */
public class OfferString_VII {

    public static void main(String[] args) {
        OfferString_VII instance = new OfferString_VII();
        List<String> ans = instance.restoreIpAddresses("0279245587303");
        System.out.println(Arrays.toString(ans.toArray()));
    }
    private List<String> ans = new ArrayList<>();
    private String s ;
    public List<String> restoreIpAddresses(String s) {
        this.s = s;
        if (s.length()<4)return ans;
        dfs(0,4,new StringBuilder());
        return ans;
    }

    private void dfs(int start,int last,StringBuilder sb) {
        if (last==0)return ;
        if (last == 1){
            if (start>=s.length())return;
            String substring = new String(s.substring(start)) ;
            if (substring.charAt(0) == '0'&&substring.length()>1)return;
            long p = Long.parseLong(substring);
            if (p>255)return;
            sb.append(p);
            ans.add(sb.toString());
            return;
        }
        for (int i = 1;i<=3;i++) {
            if (start+i>s.length())return;
            String substring = new String(s.substring(start, start + i)) ;
            if (substring.charAt(0) == '0'&&substring.length()>1)continue;
            long p = Long.parseLong(substring);
            if (p >255)continue;
            int lastIdx = sb.length();
            sb.append(p).append(".");
            dfs(start+i,last-1,sb);
            sb.delete(lastIdx,sb.length());
        }
    }
}
